"""
题目:给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

    示例：
    二叉树：[3,9,20,null,null,15,7],

        3
    / \
    9  20
        /  \
    15   7
    返回其层序遍历结果：
    [
    [3],
    [9,20],
    [15,7]
    ]

解题思路：层序遍历二叉树，最直观的想法就是保留每一层的叶子值，然后再把所有层的值放到一个list中，作为最终结果返回。但是重点是怎么知道哪些节点是某一层的叶子节点，
         而不会跨层取值，我们可以设置一个灵活变量queue，它每次都只保存一层的叶子节点，当我们访问下一层时，此时的queue中会将上一层的叶子节点删除。具体做法就是：
         首先把根结点放到queue中，然后计算当前queue的长度n，我们就会知道当前层共有多少个节点，之后循环n次，把每一次取出的当前层的节点的左右节点放到queue中，
         最后再删除queue中的n个节点，即可把当前层删除，只保留下一层的节点，循环做下去，直到所有节点遍历完成即可。

时间复杂度：O(N)
空间复杂度：O(N)
"""
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        queue = []
        res = []
        if root:
            queue.append(root)
        while queue:
            n = len(queue)
            level = []
            for i in range(n):
                node = queue[i]
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                level.append(node.val)
            del queue[:n]
            res.append(level)
        return res
